home *** CD-ROM | disk | FTP | other *** search
/ Power Programmierung 2 / Power-Programmierung CD 2 (Tewi)(1994).iso / c / library / dos / diverses / leda / incl / ab_tree.h next >
Encoding:
C/C++ Source or Header  |  1991-11-15  |  6.3 KB  |  210 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  2.1.1                                                 11-15-1991
  4. +
  5. +
  6. +  ab_tree.h
  7. +
  8. +
  9. +  Copyright (c) 1991  by  Max-Planck-Institut fuer Informatik
  10. +  Im Stadtwald, 6600 Saarbruecken, FRG     
  11. +  All rights reserved.
  12. + 
  13. *******************************************************************************/
  14.  
  15.  
  16.  
  17.  
  18.  
  19. #ifndef AB_TREE_H
  20. #define AB_TREE_H
  21.  
  22. //------------------------------------------------------------------------------
  23. //
  24. // (a,b)-trees 
  25. //
  26. // Evelyn Haak, Juergen Dedorath, and Dirk Basenach   (1989)
  27. //
  28. // Implementation follows
  29. // Kurt Mehlhorn : "Data Structures and Algorithms 1", section III, 5.2 - 5.3
  30. //
  31. // Modifications:
  32. // -------------
  33. //
  34. // - member-function insert_at_node added  ( Michael Wenzel , Nov. 89)
  35. //
  36. // - virtual compare function ( Michael Wenzel , Nov. 89)
  37. //
  38. // - delete : overwrite copies of inner nodes by
  39. //            following links between different
  40. //            instances of the same key    ( Michael Wenzel , Jan. 90)
  41. //
  42. // - virtual clear functions  ( S. Naeher, Mai 90)
  43. //
  44. //------------------------------------------------------------------------------
  45.  
  46. #include    <LEDA/basic.h>
  47.  
  48. //------------------------------------------------------------------------------
  49. //  some declarations
  50. //------------------------------------------------------------------------------
  51.  
  52.  
  53. class ab_tree;
  54. class ab_tree_node;
  55.  
  56. typedef ab_tree_node* abnode;
  57.  
  58. typedef ab_tree_node* ab_tree_item;
  59.  
  60.  
  61. /*------------------------------------------------------------*/
  62. /*  class ab_tree_node                                        */
  63. /*------------------------------------------------------------*/
  64.  
  65. class ab_tree_node {
  66.   friend class ab_tree;
  67.  
  68.   friend void concat(ab_tree& s1,ab_tree& s2,ab_tree_node* current,ent cur_key);
  69.   friend void pr_ab_tree(ab_tree_node* localroot,int blancs);
  70.   friend void del_ab_tree(ab_tree_node* localroot);
  71.  
  72.  
  73.   int p;           /* number of sons,a<=p<=b,0 iff leave*/
  74.   int height;      /* height of node*/
  75.   int index;       /* v is index'th son of his father*/
  76.   ab_tree_node* father;   
  77.   ent* k;          /* array[1..b] --------------------------  */
  78.                          //-----------------------------------
  79.                          /*to every node v of T we assign p(v)-1 */
  80.                          /*elements k[1](v),...,k[p(v)-1](v) of U*/
  81.                          /* such that for all i (1<i<p(v)-1):*/
  82.                          /* k[i](v) < k[i+1](v) and for all leaves*/
  83.                          /* w in the i-th subtree of v we have*/
  84.                          /* k[i-1] < key[w] <= k[i](v) */
  85.                          /*------------------------------------*/
  86.                          /* if v is a leave ==> k[1]=key[v]*/
  87.  
  88.                          
  89.   ab_tree_node** son;    /* array [1..b+1] of pointer to sons*/
  90.   ab_tree_node** same;   /* m.w. : links between same keys */
  91.                          /* array [1..b]                   */
  92.   ent inf;
  93.  
  94. /* size = 8 words  */
  95.  
  96. public:
  97.  
  98.   ab_tree_node(int p,int height,int index,ab_tree_node* father,int b);
  99.  
  100.  ~ab_tree_node();
  101.  
  102.    OPERATOR_NEW(8)
  103.    OPERATOR_DEL(8)
  104.  
  105.  }; 
  106.   
  107. /*-----------------------------------------------------------------*/
  108. class ab_tree   
  109.    {
  110.  
  111.     friend class ab_tree_node;
  112.  
  113.     friend void concat(ab_tree&,ab_tree&,ab_tree_node*,ent); 
  114.  
  115.  
  116.     friend void pr_ab_tree(ab_tree_node* localroot,int blancs);
  117.     friend void del_ab_tree(ab_tree_node* localroot);
  118.  
  119.     int a;
  120.     int b;
  121.  
  122.     int height;             /* height of tree   */
  123.     int count;              /* number of leaves */
  124.  
  125.     ab_tree_node* root;
  126.     ab_tree_node* minimum;  
  127.     ab_tree_node* maximum;
  128.  
  129.     ab_tree_node* expand(ab_tree_node* v,int i);
  130.  
  131.     void split_node(ab_tree_node* v);
  132.     void share(ab_tree_node* v,ab_tree_node* y,int direct);
  133.     void fuse (ab_tree_node* v,ab_tree_node* w);
  134.     void del_tree(ab_tree_node* localroot);
  135.     void exchange_leaves(ab_tree_node*, ab_tree_node*);
  136.     void pr_ab_tree(ab_tree_node*,int) const;
  137.  
  138.  
  139.  
  140.     ab_tree_node* copy_ab_tree(ab_tree_node*,abnode&,int) const;
  141.  
  142.     virtual int cmp(ent& x,ent& y) const { return int(x)-int(y); }
  143.  
  144.     virtual void clear_key(ent& x) const { Clear(x); }
  145.     virtual void clear_inf(ent& x) const { Clear(x); }
  146.  
  147.     virtual void copy_key(ent& x)  const { Copy(x);  }
  148.     virtual void copy_inf(ent& x)  const { Copy(x);  }
  149.  
  150.     virtual void print_key(ent& x) const { Print(x); }
  151.     virtual void print_inf(ent& x) const { Print(x); }
  152.  
  153. public:
  154.  
  155.  
  156.  
  157.     void clear();
  158.  
  159.     ent  inf(ab_tree_node* p)  const { return p->inf; }
  160.     ent  key(ab_tree_node* p)  const { return p->k[1]; }
  161.  
  162.     ab_tree_node* insert(ent, ent);
  163.     ab_tree_node* insert_at_node(ab_tree_node*, ent, ent);
  164.     ab_tree_node* locate(ent) const;
  165.     ab_tree_node* locate_pred(ent) const;
  166.     ab_tree_node* lookup(ent) const;
  167.  
  168.     void del(ent);
  169.     void del_node(ab_tree_node*);
  170.     void change_inf(ab_tree_node*, ent);
  171.     void flip(ab_tree_node*, ab_tree_node*);
  172.     void reverse(ab_tree_node*, ab_tree_node*);
  173.  
  174.     ab_tree& conc(ab_tree&);
  175.     void split_at_item(ab_tree_node* w,ab_tree& L,ab_tree& R);
  176.  
  177.     void del_item(ab_tree_node* p) { del_node(p); }
  178.     void del_min()                 { if (minimum) del_item(minimum); }
  179.     void decrease_key(ab_tree_node* p, ent k) { ent i = p->inf;
  180.                                                 copy_key(i);
  181.                                                 del_item(p);
  182.                                                 insert(k,i);
  183.                                                 clear_key(i);
  184.                                                }
  185.  
  186.  
  187.     bool member(ent k)  const { return (lookup(k))? true: false ; }
  188.  
  189.     ab_tree_node* min()                      const { return minimum; }
  190.     ab_tree_node* find_min()                 const { return minimum; }
  191.     ab_tree_node* max()                      const { return maximum; }
  192.     ab_tree_node* first_item()               const { return minimum; }
  193.     ab_tree_node* next_item(ab_tree_node* p) const { return p->son[2]; }
  194.     ab_tree_node* succ(ab_tree_node* p)      const { return p->son[2]; }
  195.     ab_tree_node* pred(ab_tree_node* p)      const { return p->son[1]; }
  196.  
  197.     int  size()  const { return count;       }
  198.     bool empty() const { return (count==0) ? true : false;   }
  199.     void print() const { pr_ab_tree(root,1); }
  200.  
  201.     ab_tree(int a_=2,int b_=4); 
  202.     ab_tree(const ab_tree& T);
  203.  
  204.     ab_tree& operator=(const ab_tree&);
  205.  
  206.    ~ab_tree(){ clear(); }
  207.  };
  208.  
  209. #endif
  210.